【题解】[NOIP模拟 9.29]matrix

发表于 | 分类于 | 误人子弟 个
字数统计: 717 | 阅读时长 ≈ 3

题目描述

求出满足以下条件的 n*m 的 01 矩阵个数：

  1. 第 i 行第 1~li 列恰好有 1 个 1。
  2. 第 i 行第 ri~m 列恰好有 1 个 1。
  3. 每列至多有 1 个 1。

补：li~ri中不能放 1（写的时候直接默认如此了不如初三小哥观察仔细）

输入数据

第一行两个整数 n,m。接下来 n 行每行 2 个整数 li,ri。

输出数据

一行一个整数表示答案。对 998244353 取模。

样例输入

2 6
2 4
5 6

样例输出

12

数据范围

对于 20% 的数据，n,m <= 12。
对于 40% 的数据，n,m <= 50。
对于 70% 的数据，n,m <= 300。
对于 100% 的数据，n,m <= 3000，1 <= li < ri <= m。

解题思路

一道比较抽象的动态规划题。

打代码时一边写一边忘，一边忘一边写，所以写篇博客加深记忆。

因为每列只能放一个 1，所以我们可以把它拍成 1 行来考虑。

f[ i ][ j ]表示前 i 列共放置了 j 个右区间 1 的方案数。（拒绝感性理解）

转移方程：

枚举 i，加上放或者不放右区间 1 的方案数。
越过左区间右端点时乘上需要放置的左区间 1 的方案数。

具体可参考代码注释。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <iostream>
#include <cmath>
#define re register long long
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define drep(i,a,b) for(re i=a;i>=b;--i)
typedef long long ll;
using namespace std;
const int MOD=998244353;
inline ll read(){
    ll x=0;bool f=0;char ch=getchar();
    while(!isdigit(ch)) f^=!(ch^'-'),ch=getchar();
    while(isdigit(ch)) x=((x+(x<<2))<<1)+(ch^48),ch=getchar();
    return f?-x:x;
}
inline void Online_Judge(){
	#ifndef ONLINE_JUDGE
		freopen("matrix.in","r",stdin);
		freopen("matrix.out","w",stdout);
	#endif
}
ll n,m,l[3050],r[3050],f[3050][3050],lll[3050],rr[3050];
int main(){
//    Online_Judge();
    f[0][0]=1;
	n=read(),m=read();
	rep(i,1,n){
		l[i]=read(),r[i]=read();
		lll[l[i]]++;
		rr[r[i]]++;
	}
	rep(i,1,m){
        lll[i]+=lll[i-1];
		rr[i]+=rr[i-1];
		//统计区间放置 1 数量前缀和
		f[i][0]=f[i-1][0];
		rep(j,1,i) f[i][j]=f[i-1][j-1]*(rr[i]-(j-1))+f[i-1][j],f[i][j]%=MOD;
		//分别举出第 i 列放右区间 1 或不放右区间 1 时的方案数求和并取模
		rep(j,lll[i-1],lll[i]-1) rep(k,0,i) f[i][k]=f[i][k]*(i-k-j),f[i][k]%=MOD;
		//rep(j,lll[i-1],lll[i]-1) 表示左区间需要再放置 lll[ i ]-lll[ i-1 ] 个 1。
		//乘上前 i 列共放 k 个右区间 1 时左区间 1 放置方案数并取模
	}
	printf("%lld\n",f[m][n]);

	return 0;
}

题目来源

暂无

0%